#include <iostream>
#include <string>
#include <map>
#include <list>
#include <algorithm>
using namespace std;
class LRUCache {
    struct Node {
        int key, value;
        Node(int k, int v) : key(k), value(v) {}
    };
public:
    LRUCache(int capacity) : _capacity(capacity) {}

    int get(int key) {
        if (!_hash.count(key)) return -1;

        auto it = _hash[key];
        Node node = *it;
        _cache.erase(it);
        _cache.push_front(node);
        _hash[key] = _cache.begin();

        return node.value;
    }

    void put(int key, int value) {
        if (_hash.count(key)) {
            auto it = _hash[key];
            _cache.erase(it);
            _cache.push_front(Node(key, value));
            _hash[key] = _cache.begin();
        }
        else {
            if (_cache.size() >= _capacity) {
                int key = _cache.back().key;
                _cache.pop_back();
                _hash.erase(key);
            }

            _cache.push_front(Node(key, value));
            _hash[key] = _cache.begin();
        }
    }
private:
    int _capacity;
    list<Node> _cache;
    map<int, list<Node>::iterator> _hash; // key 到 it
};

int main()
{
	int n; cin >> n;
	LRUCache lru(n);
	string flag;
	while (cin >> flag) {
		if (flag == "put") {
			int k, v; cin >> k >> v;
			lru.put(k, v);
		}
		if (flag == "get") {
			int k; cin >> k;
			cout << lru.get(k) << endl;
		}
	}
	return 0;
}